1. Field of the Invention
The present invention relates to performing serial binary arithmetic from most significant bit to least significant bit. The binary arithmetic includes addition, subtraction, and multiplication.
2. Description of the Related Art
In the past, arithmetic operations such as multiplication were performed on two parallel binary numbers to produce a parallel output. This type of multiplication has several disadvantages. One disadvantage is that the amount of hardware increases as the square of the number of bits in the words being multiplied. In addition, parallel multiplication does not take advantage of the most significant bit (MSB) to least significant bit (LSB) ordering that occurs in most sorting operations, and in successive approximation analog to digital converters.
Serial arithmetic operations resolve the aforementioned short comings of parallel multiplication. In serial multiplication numbers are multiplied using inputs which are received from MSB to LSB. One advantage offered by this arrangement is that the amount of circuitry increases linearly with the number of bits in the input words, rather than as the square of the number of bits. In addition, serial arithmetic takes advantage of the MSB to LSB ordering used in most sorting operations, and in successive approximation analog to digital converters. Serial operations also facilitate pipelining by overlapping operations. For example, the most significant bit of a first arithmetic operation can be received by a second arithmetic operation without waiting for the first operation to produce less significant bits.
Since serial arithmetic operations produce the MSB before producing the LSB, the final value of the most significant bits may not be known until the last pair of least significant bits have been received at an input. This characteristic of serial arithmetic requires representing an interim result in a redundant manner. A redundant result P, which uses a signed digit representation, can be expressed as: ##EQU1## The interim result is then converted into an ordinary binary number to produce a final result.
A signed digit representation is disclosed in existing works such as "On-Line Arithmetic: An Overview", M. D. Ercegovac, SPIE Vol. 495 Real Time Signal Processing VII, pp 86-93, 1984; "On-The-Fly Conversion of Redundant into Conventional Representations", M. D. Ercegovac and T. Lang, IEEE Transactions on Computers, Vol. C-36, No. 7, pp 895-897, July 1987; "Signed-Digit Number Representations for Fast Parallel Arithmetic", A. Avizienis, IRE Transactions on Electronic Computers, Vol. EC-10, pp 389-400, Sept. 1961. The contents of said existing works are hereby incorporated by reference. By employing a signed digit representation, the existing works require complex hardware that performs both addition and subtraction.